// LinkedList.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <memory>
#include <array>

using namespace std;

struct ListNode {
    int val;
    shared_ptr<ListNode> next;
    ListNode(int x) : val(x), next(nullptr) { }
};

shared_ptr<ListNode> reverseLinkedList(shared_ptr<ListNode> root, int n)
{
    if (!root)
    {
        return nullptr;
    }

    if (n == 0)
    {
        return root->next;
    }
    else if (n == 1)
    {
        swap(root->val, root->next->val);
        return root->next->next;
    }
    else
    {
        auto nth = reverseLinkedList(root->next, n - 2);
        swap(root->val, nth->val);
        return nth->next;
    }
}

void reverseLinkedList(shared_ptr<ListNode> root, int m, int n)
{
    if (!root)
    {
        throw out_of_range("root is empty.");
    }

    auto current = root;
    for (int i = 1; i < m; ++i)
    {
        if (!current)
        {
            throw out_of_range("m exceeds the list.");
        }
        current = current->next;
    }

    reverseLinkedList(current, n-m);
}

template<typename T, size_t N>
shared_ptr<ListNode> makeList(array<T, N> const& data)
{
    shared_ptr<ListNode> root;
    auto current = root;
    for (size_t i = 0; i < data.size(); ++i) 
    {
        if (!root)
        {
            root = make_shared<ListNode>(data[i]);
            current = root;
        }
        else
        {
            current->next = make_shared<ListNode>(data[i]);
            current = current->next;
        }
    }
    return root;
}

void outputList(shared_ptr<ListNode> const& root)
{
    auto current = root;
    while (current)
    {
        cout << current->val << ", ";
        current = current->next;
    }
    cout << endl;
}

void testReverseLinkedList()
{
    //Reverse a linked list from position m to n. Do it in-place and in one-pass.
    //For example: Given 1->2->3->4->5->nullptr, m = 2 and n = 4,
    //return 1->4->3->2->5->nullptr.
    //Note: Given m, n satisfy the following condition: 1  m  n  length of list.
    array<int, 9> data = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    auto root = makeList(data);

    try
    {
        reverseLinkedList(root, 2, 8);
    }
    catch (std::out_of_range const&)
    {
    }

    outputList(root);
}

shared_ptr<ListNode> partitionList(shared_ptr<ListNode> root, int x)
{
    shared_ptr<ListNode> low;
    shared_ptr<ListNode> high;
    shared_ptr<ListNode> currentLow;
    shared_ptr<ListNode> currentHigh;

    shared_ptr<ListNode> current = root;
    while (current)
    {
        if (current->val < x)
        {
            if (!low)
            {
                low = current;
            }
            else
            {
                currentLow->next = current;
            }
            currentLow = current;
        }
        else 
        {
            if (!high)
            {
                high = current;
            }
            else
            {
                currentHigh->next = current;
            }
            currentHigh = current;
        }

        current = current->next;
    }

    currentLow->next = high;
    currentHigh->next.reset();
    return low;
}

void testPartitionList()
{
    //Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater
    //than or equal to x.
    //You should preserve the original relative order of the nodes in each of the two partitions.
    //For example, Given 1->4->3->2->5->2 and x = 3, return 1->2->2->4->3->5.
    array<int, 6> data = {1, 4, 3, 2, 5, 2};
    shared_ptr<ListNode> root = makeList(data);
    auto result = partitionList(root, 3);
    outputList(result);
}

void removeDuplicates(shared_ptr<ListNode> root)
{

}

void testRemoveDuplicates()
{
    //Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers
    //from the original list.
    //For example,
    //Given 1->2->3->3->4->4->5, return 1->2->5.
    //Given 1->1->1->2->3, return 2->3.

    array<int, 6> data = {1, 1, 2, 3, 3};
    shared_ptr<ListNode> root = makeList(data);
    removeDuplicates(root);
    outputList(root);
}

shared_ptr<ListNode> rotate(shared_ptr<ListNode> root, int k)
{
    //assume k is less than the length of the given list
    auto slow = root;
    auto fast = root;
    for (int i = 0; i < k; ++i)
    {
        fast = fast->next;
    }

    while (fast->next)
    {
        slow = slow->next;
        fast = fast->next;
    }

    fast->next = root;
    root = slow->next;
    slow->next.reset();
    return root;
}

void testRotateList()
{
    //Given a list, rotate the list to the right by k places, where k is non-negative.
    //For example: Given 1->2->3->4->5->nullptr and k = 2, return 4->5->1->2->3->nullptr.
    array<int, 5> data = {1, 2, 3, 4, 5};
    shared_ptr<ListNode> root = makeList(data);
    root = rotate(root, 2);
    outputList(root);
}

shared_ptr<ListNode> shift(shared_ptr<ListNode> root, int k)
{
    //assume k is less than the length of the list.
    auto ret = root;
    for (int i = 0; i < k; ++i)
    {
        ret = ret->next;
    }
    return ret;
}

shared_ptr<ListNode> reversNodes(shared_ptr<ListNode> root, int k)
{
    if (k == 0)
    {
        return nullptr;
    }
    else if (k == 1)
    {
        return root->next;
    }
    else if (k == 2)
    {
        auto other = root->next;
        if (!other)
        {
            return nullptr;
        }
        swap(root->val, other->val);
        return other->next;
    }

    auto other = reversNodes(root->next, k - 2);
    if (!other)
    {
        return nullptr;
    }
    swap(root->val, other->val);
    return other->next;

}

void testReversNodes()
{
    //Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
    //If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
    //You may not alter the values in the nodes, only nodes itself may be changed.
    //Only constant memory is allowed.
    //For example, Given this linked list: 1->2->3->4->5
    //For k = 2, you should return: 2->1->4->3->5
    //For k = 3, you should return: 3->2->1->4->5
    array<int, 8> data = {1, 2, 3, 4, 5, 6, 7, 8};
    shared_ptr<ListNode> root = makeList(data);
    auto current = root;
    while (current)
    {
        current = reversNodes(current, 3);
    }
    outputList(root);
}

void testCopyList()
{
    //A linked list is given such that each node contains an additional random pointer which could point to
    //any node in the list or null.
    //Return a deep copy of the list.
}

int _tmain(int argc, _TCHAR* argv[])
{
    testReverseLinkedList();
    testPartitionList();
    testRemoveDuplicates();
    testRotateList();
    testReversNodes();
    testCopyList();
    cin.get();
    return 0;
}

